/*
 * @lc app=leetcode.cn id=105 lang=cpp
 *
 * [105] 从前序与中序遍历序列构造二叉树
 *
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
 *
 * algorithms
 * Medium (70.98%)
 * Likes:    1537
 * Dislikes: 0
 * Total Accepted:    337.1K
 * Total Submissions: 474.8K
 * Testcase Example:  '[3,9,20,15,7]\n[9,3,15,20,7]'
 *
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder
 * 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 
 * 
 * 
 * 示例 1:
 * 
 * 
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 * 
 * 
 * 
 * 
 * 提示:
 * 
 * 
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder 和 inorder 均 无重复 元素
 * inorder 均出现在 preorder
 * preorder 保证 为二叉树的前序遍历序列
 * inorder 保证 为二叉树的中序遍历序列
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //定义 新的vector 
    // TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    //     if(preorder.size() == 0) return NULL;
    //     int preorderVal = preorder[0];
    //     TreeNode* root = new TreeNode(preorderVal);

    //     //确定该元素在中序序列位置
    //     int preorderValIndex;
    //     for (int i = 0; i < inorder.size(); i++) {
    //         if(inorder[i] == preorderVal) {
    //             preorderValIndex = i;
    //             break;
    //         }
    //     }

    //     //划分中序序列
    //     vector<int> inorderLeft(inorder.begin(), inorder.begin()+preorderValIndex);
    //     vector<int> inorderRight(inorder.begin()+preorderValIndex+1, inorder.end());

    //     //划分前序序列
    //     int size = inorderLeft.size();
    //     vector<int> preorderLeft(preorder.begin()+1, preorder.begin()+1+size);
    //     vector<int> preorderRight(preorder.begin()+1+size, preorder.end());

    //     root->left = buildTree(inorderLeft, preorderLeft);
    //     root->right = buildTree(inorderRight, preorderRight);

    //     return root;

        
    // }


    TreeNode* traversal(vector<int>& preorder, int preorderBegin, int preorderEnd, vector<int>& inorder, int inorderBegin, int inorderEnd){
        if(preorderBegin == preorderEnd) return NULL;
        
        int rootVal = preorder[preorderBegin];
        TreeNode* root = new TreeNode(rootVal);
       
        if(preorderEnd - preorderBegin == 1) return root;

        int rootValInorderIndex;
        for(rootValInorderIndex = inorderBegin; rootValInorderIndex < inorderEnd; rootValInorderIndex++) {
            if(inorder[rootValInorderIndex] == rootVal) break;
        }

        //划分中序序列
        int inorderLeftBegin = inorderBegin;
        int inorderLeftEnd = rootValInorderIndex;
        int inorderRightBegin = rootValInorderIndex + 1;
        int inorderRightEnd = inorderEnd;

        //划分后序序列
        int preorderLeftBegin = preorderBegin + 1;
        int preorderLeftEnd = preorderBegin + 1 + inorderLeftEnd - inorderLeftBegin;
        int preorderRightBegin = preorderBegin + 1 + inorderLeftEnd - inorderLeftBegin;
        int preorderRightEnd = preorderEnd;

        root->left = traversal(preorder, preorderLeftBegin, preorderLeftEnd, inorder, inorderLeftBegin, inorderLeftEnd);
        root->right = traversal(preorder, preorderRightBegin, preorderRightEnd, inorder, inorderRightBegin, inorderRightEnd);

        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return NULL;
        return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};
// @lc code=end

